package ahaArithmetic;

//宝岛探险 广度优先解法
public class Bfs_3 {

    static int[][] map = new int[][]{
            {1,2,1,0,0,0,0,0,2,3},
            {3,0,2,0,1,2,1,0,1,2},
            {4,0,1,0,1,2,3,2,0,1},
            {3,2,0,0,0,1,2,4,0,0},
            {0,0,0,0,0,0,1,5,3,0},
            {0,1,2,1,0,1,5,4,3,0},
            {0,1,2,3,1,3,6,2,1,0},
            {0,0,3,4,8,9,7,5,0,0},
            {0,0,0,3,7,8,6,0,1,2},
            {0,0,0,0,0,0,0,0,1,0}
    };
    static Node_3[] nodes = new Node_3[2501];
    static int startX=6,startY=8;
    static int x = startX , y = startY;
    static int head = 0;
    static int tail = 1;
    static int[][] next = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    static int result = 1;

    public static void main(String[] args) {
        for(int i=0;i<nodes.length;i++){
            nodes[i] = new Node_3();
        }
        nodes[head].x = startX;
        nodes[head].y = startY;
        map[startX][startY] = -1;
        bfs_3();
        System.out.println(result);
    }

    public static void bfs_3(){
        while (tail>head) {
            for (int i = 0; i <= 3; i++) {
                x += next[i][0];
                y += next[i][1];
                //判断越界
                if (x < 0 || x > 9 || y < 0 || y > 9) {
                    x -= next[i][0];
                    y -= next[i][1];
                    continue;
                }
                //判断海洋
                if (map[x][y] <= 0) {
                    x -= next[i][0];
                    y -= next[i][1];
                    continue;
                }
                //写入队列
                nodes[tail].x = x;
                nodes[tail].y = y;
                tail++;
                result++;
                map[x][y] = -1;
            }
            head++;
            x = nodes[head].x;
            y = nodes[head].y;
        }
    }
}

class Node_3{
    int x;
    int y;
}
